package sort;

/**
 * @description: 复习快排思路、写法
 * @author: w_jingbo
 * @date: 2023/9/18
 * @Copyright: 博客：http://coisini.wang
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[] {3 , 1, 4 , 2, 2 ,1 ,3} ;
        process(arr,0, arr.length-1);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    public static void process(int[] arr , int L , int R){
        if(L >= R){
            return;
        }
        //随机取一个数，把他放到数组尾，并用他做partition
        swap(arr,L + (int)(Math.random()*(R - L + 1)),R ) ;
        // 返回的是相等部分的左右下标
        int[] equalArea = partition(arr,L,R) ;
        process(arr,L,equalArea[0] - 1) ;
        process(arr,equalArea[1] + 1, R) ;

    }

    public static int[] partition(int[] arr , int L ,int R){
        if(L == R){
            return new int[]{L,R} ;
        }
        if(L > R){
            return new int[]{-1 , -1 } ;
        }
        int less = L - 1 ;
        int more = R ;
        int index = L ;
        while(index < more){
            if(arr[index] == arr[R]){
                index++;
            }else if(arr[index] < arr[R]){
                swap(arr,index++,++less);
            }else {
                swap(arr,index,--more);
            }
        }
        swap(arr,more,R);
        return new int[]{less + 1 , more} ;
    }



    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
